package com.manman.algorithm.sort.base;

/**
 * @author: yeshengbin
 * @date: 2025/6/1 14:35
 * @description: 选择排序
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 * 原地排序：是
 */
public class SelectSort {

    public static void selectSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            // 假设当前位置是最小值的索引
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 如果最小值的索引不是当前位置，则交换元素
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        selectSort(arr);
        System.out.println("排序后的数组：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
